home *** CD-ROM | disk | FTP | other *** search
/ BCI NET 2 / BCI NET 2.iso / archives / programming / asm / adisv1_3.lha / src / ref_table.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-20  |  14.3 KB  |  579 lines
  1. /*
  2.  * Change history
  3.  * $Log:    ref_table.c,v $
  4.  * Revision 3.0  93/09/24  17:54:26  Martin_Apel
  5.  * New feature: Added extra 68040 FPU opcodes
  6.  * 
  7.  * Revision 2.1  93/07/18  22:56:51  Martin_Apel
  8.  * *** empty log message ***
  9.  * 
  10.  * Revision 2.0  93/07/01  11:54:50  Martin_Apel
  11.  * *** empty log message ***
  12.  * 
  13.  * Revision 1.18  93/07/01  11:44:25  Martin_Apel
  14.  * 
  15.  * Revision 1.17  93/06/16  20:29:30  Martin_Apel
  16.  * Bug fix: Removed strlen calls in enter_ref, when it was uncertain that
  17.  *          its parameter was NULL. ENFORCER Hits killed.
  18.  * 
  19.  * Revision 1.16  93/06/03  18:36:59  Martin_Apel
  20.  * Minor mod.: Table size for symbol table is now derived from the size of
  21.  *             the load file instead of from the sum of the hunk sizes
  22.  * 
  23.  */
  24.  
  25. #include <exec/types.h>
  26. #include <string.h>
  27. #include "defs.h"
  28. #include "refs.h"
  29.  
  30. static char rcsid [] = "$Id: ref_table.c,v 3.0 93/09/24 17:54:26 Martin_Apel Exp $";
  31.  
  32. /**********************************************************************/
  33. /* I'm using a combination of a doubly linked list and a hash table   */
  34. /*        for maintaining a data base of referenced addresses.        */
  35. /**********************************************************************/
  36.  
  37. #define HASH_FUNC(x) ((x)>>4)
  38. #define SENTINEL     0xffffffff
  39.  
  40. PRIVATE struct mem_pool *current_pool,
  41.                         *first_pool = NULL;
  42.  
  43. PRIVATE struct ref_entry **ref_table = NULL;
  44. PRIVATE struct ref_entry **active_table = NULL;
  45. PRIVATE long table_size;
  46.  
  47. /**************************************************************************/
  48.  
  49. BOOL init_ref_table (ULONG size)
  50.  
  51. {
  52. /* A marker with address 0xffffffff is placed as the very last entry
  53.    in the reference table. This speeds up all comparisons considerably.
  54. */
  55. int i;
  56. struct ref_entry *marker;
  57.  
  58. table_size = size / 16 + 2;
  59.  
  60. ref_table = get_mem (table_size * sizeof (struct ref_entry*));
  61. active_table = get_mem (table_size * sizeof (struct ref_entry*));
  62. first_pool = get_mem (sizeof (struct mem_pool) + POOLSIZE);
  63.  
  64. current_pool = first_pool;
  65. first_pool->next = NULL;
  66. first_pool->free = (POOLSIZE - sizeof (struct ref_entry)) / 2;   /* in words */
  67. first_pool->next_free = (UWORD*)(first_pool + 1);   /* ptr behind mempool */
  68. marker = (struct ref_entry*)first_pool->next_free;
  69. first_pool->next_free += sizeof (struct ref_entry) / 2;
  70.  
  71. /* Enter marker (space already reserved) */
  72.  
  73. marker->next = NULL;
  74. marker->prev = marker;
  75. marker->next_active = NULL;
  76. marker->prev_active = marker;
  77. marker->offset = SENTINEL;
  78. marker->name = NULL;
  79. marker->access = ACC_UNKNOWN;
  80.  
  81. for (i = table_size - 1; i >= 0; i--)
  82.   {
  83.   *(ref_table + i) = marker;
  84.   *(active_table + i) = marker;
  85.   }
  86.  
  87. return (TRUE);
  88. }
  89.  
  90. /**************************************************************************/
  91.  
  92. void kill_ref_table ()
  93.  
  94. {
  95. struct mem_pool *tmp, *next;
  96.  
  97. for (tmp = first_pool; tmp != NULL; tmp = next)
  98.   {
  99.   next = tmp->next;
  100.   release_mem (tmp);
  101.   }
  102.  
  103. if (ref_table)
  104.   release_mem (ref_table);
  105. if (active_table)
  106.   release_mem (active_table);
  107.   
  108. }
  109.  
  110. /**************************************************************************/
  111.  
  112. PRIVATE struct ref_entry *find_ref (ULONG offset, BOOL *found)
  113.  
  114. /* Returns a pointer to the desired ref_entry, if possible;
  115.    otherwise returns pointer to the next entry in the table
  116. */
  117. {
  118. int entry;
  119. register struct ref_entry *tmp;
  120.  
  121. entry = HASH_FUNC (offset);
  122. /* For those labels which lie outside the segment (typically from geta4 ()) */
  123. if (entry >= table_size)
  124.   entry = table_size - 1;
  125.  
  126. for (tmp = *(ref_table + entry); tmp->offset < offset; tmp = tmp->next);
  127.  
  128. if (tmp->offset == offset)
  129.   {
  130.   *found = TRUE;       /* found it */
  131.   return (tmp);
  132.   }
  133.  
  134. *found = FALSE;
  135. return (tmp);
  136. }
  137.  
  138. /**************************************************************************/
  139.  
  140. PRIVATE struct ref_entry *find_active_ref (ULONG offset, BOOL *found)
  141.  
  142. /* Returns a pointer to the desired ref_entry, if possible;
  143.    otherwise returns pointer to the next entry in the table
  144. */
  145. {
  146. int entry;
  147. register struct ref_entry *tmp;
  148.  
  149. entry = HASH_FUNC (offset);
  150. /* For those labels which lie outside the segment (typically from geta4 ()) */
  151. if (entry >= table_size)
  152.   entry = table_size - 1;
  153.  
  154. for (tmp = *(active_table + entry); tmp->offset < offset; tmp = tmp->next_active);
  155.  
  156. if (tmp->offset == offset)
  157.   {
  158.   *found = TRUE;       /* found it */
  159.   return (tmp);
  160.   }
  161.  
  162. *found = FALSE;
  163. return (tmp);
  164. }
  165.  
  166. /**************************************************************************/
  167.  
  168. BOOL find_reference (ULONG offset, char **name, UWORD *access_type)
  169.  
  170. {
  171. BOOL found;
  172. struct ref_entry *ref_entry;
  173.  
  174. ref_entry = find_ref (offset, &found);
  175. if (found)
  176.   {
  177.   *name = ref_entry->name;
  178.   *access_type = ref_entry->access;
  179.   return (TRUE);
  180.   }
  181. else
  182.   return (FALSE);
  183. }
  184.  
  185. /**************************************************************************/
  186.  
  187. BOOL find_active_reference (ULONG offset, char **name, UWORD *access_type)
  188.  
  189. {
  190. BOOL found;
  191. struct ref_entry *ref_entry;
  192.  
  193. ref_entry = find_active_ref (offset, &found);
  194. if (found)
  195.   {
  196.   *name = ref_entry->name;
  197.   *access_type = ref_entry->access;
  198.   return (TRUE);
  199.   }
  200. else
  201.   return (FALSE);
  202. }
  203.  
  204. /**************************************************************************/
  205.  
  206. void enter_ref (ULONG offset, char *name, UWORD access_type)
  207.  
  208. {
  209. /* Upon calling "enter_ref" a label is always activated */
  210.  
  211. BOOL found;
  212. struct ref_entry *tmp,
  213.                  *tmp_active,
  214.                  *new;
  215. char *string;
  216. register int index;
  217. BOOL activate = FALSE;
  218. int name_len;
  219.  
  220. tmp = find_ref (offset, &found);
  221. if (name == NULL)
  222.   name_len = 0;
  223. else
  224.   name_len = strlen (name);
  225.  
  226. if (found)
  227.   {
  228.   if ((tmp->name == NULL) && (name != NULL))
  229.     {
  230.     if (current_pool->free < (name_len + 2) / 2)
  231.       {
  232.       current_pool->next = get_mem (sizeof (struct mem_pool) + POOLSIZE);
  233.       current_pool = current_pool->next;
  234.       current_pool->free = POOLSIZE / 2;
  235.       current_pool->next_free = (UWORD*)(current_pool + 1);
  236.       current_pool->next = NULL;
  237.       }
  238.     string = (char*) current_pool->next_free;
  239.     current_pool->next_free += (name_len + 2) / 2;
  240.     current_pool->free -= (name_len + 2) / 2;
  241.     strcpy (string, name);
  242.     tmp->name = string;
  243.     }
  244.  
  245.   activate = access_type & (~tmp->access);   /* activate this label,
  246.                                                 if there's new information */
  247.   tmp->access |= access_type;
  248.   }
  249. else
  250.   {
  251.   if (current_pool->free < (sizeof (struct ref_entry) + name_len + 2) / 2)
  252.     {
  253.     current_pool->next = get_mem (sizeof (struct mem_pool) + POOLSIZE);
  254.     current_pool = current_pool->next;
  255.     current_pool->free = POOLSIZE / 2;
  256.     current_pool->next_free = (UWORD*)(current_pool + 1);
  257.     current_pool->next = NULL;
  258.     }
  259.   new = (struct ref_entry*) current_pool->next_free;
  260.   current_pool->free -= (sizeof (struct ref_entry) + name_len + 2) / 2;
  261.   current_pool->next_free += (sizeof (struct ref_entry) + name_len + 2) / 2;
  262.   
  263.   new->prev = tmp->prev;
  264.   new->next = tmp;
  265.   tmp->prev->next = new;
  266.   tmp->prev = new;
  267.  
  268.   index = HASH_FUNC (offset);
  269.   if (index >= table_size)
  270.     index = table_size - 1;
  271.   while (index >= 0 && (*(ref_table + index))->offset > offset)
  272.     *(ref_table + index--) = new;
  273.   tmp = new;
  274.  
  275.   new->offset = offset;
  276.   string = (char*)(new + 1);
  277.   new->access = access_type | ACC_NEW;
  278.   if (name != NULL)
  279.     {
  280.     strcpy (string, name);
  281.     new->name = string;
  282.     }
  283.   else
  284.     new->name = NULL;
  285.   activate = TRUE;
  286.   }
  287.  
  288. if (activate)
  289.   {
  290.   /* Enter it into the active table */
  291.   tmp_active = find_active_ref (offset, &found);
  292.   if (found)
  293.     return;        /* label is already in active list */
  294.  
  295.   tmp->access &= ~TMP_INACTIVE;
  296.   tmp->prev_active = tmp_active->prev_active;         
  297.   tmp->next_active = tmp_active;
  298.   tmp_active->prev_active->next_active = tmp;
  299.   tmp_active->prev_active = tmp;
  300.  
  301.   index = HASH_FUNC (offset);
  302.   if (index >= table_size)
  303.     index = table_size - 1;
  304.   while (index >= 0 && (*(active_table + index))->offset > offset)
  305.     *(active_table + index--) = tmp;
  306.   }
  307.  
  308. return;
  309. }
  310.  
  311. /**************************************************************************/
  312.  
  313. ULONG ext_enter_ref (ULONG offset, ULONG hunk, char *name, UWORD access_type)
  314.  
  315. {
  316. /* enter_ref for addresses which lie outside their hunk.
  317.    ext_enter_ref returns a special ID under which this label
  318.    can be found again */
  319. ULONG reference;
  320.  
  321. if (hunk > 253)
  322.   {
  323.   fprintf (stderr, "Sorry, can't handle files with more than 253 hunks\n");
  324.   ExitADis ();
  325.   }
  326.  
  327. reference = (offset & 0x00ffffff) | ((hunk + 1) << 24);
  328. enter_ref (reference, name, access_type);
  329. return (reference);
  330. }
  331.  
  332. /**************************************************************************/
  333.  
  334. ULONG next_reference (ULONG from, ULONG to, UWORD *access)
  335.  
  336. {
  337. register struct ref_entry *tmp;
  338. register int index;
  339.  
  340. /* default case, only occurs for the end of a hunk */
  341. #ifdef DEBUG
  342. if (from >= to)
  343.   {
  344.   fprintf (stderr, "next_reference: from > to\n");
  345.   return (to);
  346.   }
  347. #endif
  348.  
  349. index = HASH_FUNC (from);
  350. if (index >= table_size)
  351.   index = table_size - 1;
  352.  
  353. for (tmp = *(ref_table + index); tmp->offset <= from; tmp = tmp->next);
  354.  
  355. if (tmp->offset >= to)
  356.   {
  357.   *access = ACC_UNKNOWN;
  358.   return (to);
  359.   }
  360. *access = tmp->access;
  361. return (tmp->offset);
  362. }
  363.  
  364. /**************************************************************************/
  365.  
  366. ULONG next_active_reference (ULONG from, ULONG to, UWORD *access)
  367.  
  368. {
  369. register struct ref_entry *tmp;
  370. register int index;
  371.  
  372. /* default case, only occurs for the end of a hunk */
  373. #ifdef DEBUG
  374. if (from >= to)
  375.   {
  376.   fprintf (stderr, "next_active_reference: from > to\n");
  377.   return (to);
  378.   }
  379. #endif
  380.  
  381. index = HASH_FUNC (from);
  382. if (index >= table_size)
  383.   index = table_size - 1;
  384.  
  385. for (tmp = *(active_table + index); tmp->offset <= from; tmp = tmp->next_active);
  386.  
  387. if (tmp->offset > to)
  388.   return (to);
  389. *access = tmp->access;
  390. return (tmp->offset);
  391. }
  392.  
  393. /**************************************************************************/
  394.  
  395. #ifdef DEBUG
  396.  
  397. void check_active_table ()
  398.  
  399. {
  400. struct ref_entry *tmp;
  401. static int call_count = 0;
  402.  
  403. call_count++;
  404. for (tmp = *active_table; tmp->offset != SENTINEL; tmp = tmp->next_active)
  405.   {
  406.   if (tmp->access & TMP_INACTIVE)
  407.     {
  408.     printf ("Found inactive label in active table\n");
  409.     printf ("Called %d times\n", call_count);
  410.     }
  411.   }
  412. }
  413.  
  414. #endif
  415.  
  416. /**************************************************************************/
  417.  
  418. void deactivate_labels (ULONG from, ULONG to)
  419.  
  420. {
  421. /* Removes all labels in the range "from" to "to" from the active list.
  422.    (excluding "to" itself) */
  423. BOOL found;
  424. struct ref_entry *tmp,
  425.                  *next;
  426. int index;
  427.  
  428. tmp = find_active_ref (from, &found);
  429. while (tmp->offset < to)
  430.   {
  431.   next = tmp->next_active;
  432.   next->prev_active = tmp->prev_active;
  433.   tmp->prev_active->next_active = next;
  434.   tmp->prev_active = tmp->next_active = NULL;
  435.   tmp->access |= TMP_INACTIVE;
  436.   tmp = next;
  437.   }
  438.  
  439. index = HASH_FUNC (to);
  440. if (index >= table_size)
  441.   index = table_size - 1;
  442. while (index >= 0 && (*(active_table + index))->offset >= from)
  443.   *(active_table + index--) = tmp;
  444. }
  445.  
  446. /**************************************************************************/
  447.  
  448. void make_labels_permanent ()
  449.  
  450. {
  451. struct ref_entry *current_entry;
  452.  
  453. for (current_entry = *ref_table; current_entry->offset != SENTINEL; 
  454.      current_entry = current_entry->next)
  455.   current_entry->access &= ~(ACC_NEW | TMP_INACTIVE);
  456. }
  457.  
  458. /**************************************************************************/
  459.  
  460. void delete_tmp_labels ()
  461.  
  462. {
  463. struct ref_entry *current_entry;
  464.  
  465. /* It's not possible to free the memory of deleted labels now,
  466.    it's automatically freed by kill_ref_table () at the end
  467.    of the program */
  468.  
  469. for (current_entry = *ref_table; current_entry->offset != SENTINEL; 
  470.      current_entry = current_entry->next)
  471.   {
  472.   if (current_entry->access & ACC_NEW)
  473.     {
  474.     ULONG offset;
  475.     int index;
  476.  
  477.     current_entry->prev->next = current_entry->next;
  478.     current_entry->next->prev = current_entry->prev;
  479.     offset = current_entry->offset;
  480.     index = HASH_FUNC (offset);
  481.     if (index >= table_size)
  482.       index = table_size - 1;
  483.     while (index >= 0 && (*(ref_table + index))->offset == offset)
  484.       *(ref_table + index--) = current_entry->next;
  485.  
  486.     /* Remove it from the active table as well */
  487.     if (current_entry->next_active != NULL)
  488.       {
  489.       current_entry->prev_active->next_active = current_entry->next_active;
  490.       current_entry->next_active->prev_active = current_entry->prev_active;
  491.       offset = current_entry->offset;
  492.       index = HASH_FUNC (offset);
  493.       if (index >= table_size)
  494.         index = table_size - 1;
  495.       while (index >= 0 && (*(active_table + index))->offset == offset)
  496.         *(active_table + index--) = current_entry->next_active;
  497.       }
  498.     }
  499.   else if (current_entry->access & TMP_INACTIVE)
  500.     {
  501.     struct ref_entry *tmp_active;
  502.     int index;
  503.     BOOL found;
  504.     ULONG offset;
  505.  
  506.     current_entry->access &= ~TMP_INACTIVE;
  507.     offset = current_entry->offset;
  508.     tmp_active = find_active_ref (offset, &found);
  509.     if (found)
  510.       fprintf (stderr, "INTERNAL ERROR: delete_tmp_labels: TMP_INACTIVE label in active list at address %lx\n", offset);
  511.     current_entry->prev_active = tmp_active->prev_active;         
  512.     current_entry->next_active = tmp_active;
  513.     tmp_active->prev_active->next_active = current_entry;
  514.     tmp_active->prev_active = current_entry;
  515.  
  516.     index = HASH_FUNC (offset);
  517.     if (index >= table_size)
  518.       index = table_size - 1;
  519.     while (index >= 0 && (*(active_table + index))->offset > offset)
  520.       *(active_table + index--) = current_entry;
  521.     }
  522.   }
  523. }
  524.  
  525. /**************************************************************************/
  526.  
  527. #ifdef DEBUG
  528. void print_ref_table (ULONG from, ULONG to)
  529.  
  530. {
  531. register struct ref_entry *tmp;
  532. int i;
  533.  
  534. printf ("References by chain\n");
  535. i = HASH_FUNC (from);
  536. for (tmp = *(ref_table + i); tmp->offset < to; tmp = tmp->next)
  537.   {
  538.   printf ("%06lx: Access: %04lx, %s\n", tmp->offset, tmp->access,
  539.           tmp->name);
  540.   }
  541. /*
  542. printf ("References by index:\n");
  543. for (i = HASH_FUNC (from); i < HASH_FUNC (to); i++)
  544.   printf ("First entry in chain %x: %lx\n", i, (*(ref_table + i))->offset);
  545. */
  546. }
  547.  
  548. void print_active_table (ULONG from, ULONG to)
  549.  
  550. {
  551. register struct ref_entry *tmp;
  552. int i;
  553.  
  554. printf ("References by chain\n");
  555. i = HASH_FUNC (from);
  556. for (tmp = *(active_table + i); tmp->offset < to; tmp = tmp->next_active)
  557.   {
  558.   printf ("%06lx: Access: %04lx, %s\n", tmp->offset, tmp->access,
  559.           tmp->name);
  560.   }
  561. /* 
  562. printf ("References by index:\n");
  563. for (i = HASH_FUNC (from); i < HASH_FUNC (to); i++)
  564.   printf ("First entry in chain %x: %lx\n", i, (*(active_table + i))->offset);
  565. */
  566. }
  567.  
  568.  
  569. BOOL ref_exists (ULONG offset)
  570.  
  571. {
  572. char *dummy;
  573. UWORD access;
  574.  
  575. return (find_reference (offset, &dummy, &access));
  576. }
  577.  
  578. #endif
  579.